package mao.leetcode.others.leetcode108;

public class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0) return null;
        return sortedArrayToBST_helper(nums,0,nums.length-1);
    }
    public TreeNode sortedArrayToBST_helper(int[] nums,int start,int end) {
        if (start > end) return null;
        if (start == end) return new TreeNode(nums[start]);
        int mid = start+(end-start)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left=sortedArrayToBST_helper(nums,start,mid-1);
        root.right=sortedArrayToBST_helper(nums,mid+1,end);
        return root;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
